package com.liang.leetcode.string;

/**
 * 459.重复的子字符串
 * 给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成。
 * 示例 1:
 *  输入: s = "abab"
 *  输出: true
 *  解释: 可由子串 "ab" 重复两次构成。
 * 示例 2:
 *  输入: s = "aba"
 *  输出: false
 * 示例 3:
 *  输入: s = "abcabcabcabc"
 *  输出: true
 *  解释: 可由子串 "abc" 重复四次构成。 (或子串 "abcabc" 重复两次构成。)
 */
public class String05_RepeatedSubstringPattern {
    public static void main(String[] args) {
        String s = "abcabc";
        boolean isRepeatedSubstring = repeatedSubstringPattern2(s);
        System.out.println(isRepeatedSubstring);

    }

    /**
     * 解法一：字符串匹配
     * 如果s由它的子串重复组成，那么s+s（去除首尾字符）一定包含s本身
     */
    public static boolean repeatedSubstringPattern(String s) {
        // return (s + s).indexOf(s, 1) != s.length();
        if (s.length() < 2) {
            return true;
        }
        String d = s + s; //d
        String substring = d.substring(1, d.length() - 1);
        return substring.contains(s);
    }

    /**
     * 解法二：枚举
     * abcdabcd
     */
    public static boolean repeatedSubstringPattern2(String s) {
        int n = s.length();
        // 子串至少需要重复一次，循环只需要遍历到字符串长度的一半
        for (int i = 1; i <= n / 2; i++) {
            // 字符串长度能被当前子串长度 i 整除
            if (n % i == 0) {
                boolean isMatch = true;
                // 字符串往后循环和子串比较，都相等才会返回 true
                // i = 2, 比较 0 2; 1 3; 0 4; 1 5; 0 6; 1 7
                for (int j = i; j < n; j++) {
                    // 如果发现不匹配的字符，标记为false，并跳出循环
                    if (s.charAt(j) != s.charAt(j - i)) {
                        isMatch = false;
                        break;
                    }
                }
                if (isMatch) {
                    return true;
                }
            }
        }
        return false;
    }

    /**
     * 方法三：KMP 算法
     */
    
}
